{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 18, 2, 8, 3, 7, 12, 14, 13, 10, 6, 15, 1, 16, 0, 9, 19, 17, 5, 11]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAdMAAAI1CAYAAACNCxCvAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzs3Xl8TFf/B/DPTPZFggSRWqK2WBMktuAJtcaa2iXWWlpUW/2VVrUoanmUUk9pLbXF8liKh2gppXYii4gitcVObJGIJJOZ3x8xEZLJNsu5c+fzfr36epW5c+d7nLn3O/d+zzlXodFoQERERMWnFB0AERGRuWMyJSIi0hOTKRERkZ6YTImIiPTEZEpERKQnJlMiIiI9MZkSERHpicmUiIhIT0ymREREemIyJSIi0pN1UTZ2d3fXeHl5GSkUIiIiaTlz5kyiRqMpU9B2RUqmXl5eiIiIKH5UREREZkShUFwvzHa8zUtERKQnJlMiIiI9MZkSERHpicmUiIhIT0ymREREemIyJSIi0hOTKRERkZ6YTImIiPTEZEpERKQnJlMiIiI9MZkSERHpicmUiIhIT0ymREREemIyJSIi0hOTKRERkZ6YTImIiPTEZEpERKQnJlMiIiI9MZkSERHpicmUiIhIT0ymREREemIyJSIi0hOTKRERkZ6YTImIiPTEZEpERKQnJlMiIiI9MZkSERHpicmUiIhIT0ymREREemIyJSIi0hOTKRERkZ6YTImIiPTEZEpERKQnJlMiIiI9MZkSERHpicmUiIhIT9aiAyAiHdIzgLuJQEoqoMoErK0AJwfAwx2wtREdHRHlwGRKJDVJKUDCHeDR06w/azSvXlMqgGu3ATdXoGJ5wMVJTIxE9BomUyIpuX0fuHwTUKvzfl39MrEmPgEeJQFVKwCeZU0XHxHliTVTIqnIJ5HG30yAfbsAhM746tVfqtVZ29++b8IgiSgvTKZEUpCUku8V6Zjv58Lfu3buF7QJ9VmKkQMkovwwmRJJQcIdnYl04/69KOlcAu809M/7vWp11vuJSBgmUyLR0jNeDTZ6Q1JKMr7+5SfMH/1x/vt4+DRrP0QkBJMpkWh3E3W+9NXKpXgvqBsqlC2X/z4UAO49NGxcRFRoHM1LJFpK6uvTX16Kjr+IP86cQtSysIL3odYAyc+NEBwRFQaTKZFoqsw8//pg9Blcu3sHlfp0AQAkp6YiU63G+RGhiFy2rtD7ISLjYzIlEs3aKs+/Htn1XfRr0z77z/M2rcO1u3ewZPznRdoPERkfkymRaE4OgEKR61avo709HO3ts//s7OAIe1tblClZKvc+lArA2dHYkRKRDkymRKJ5uGctEViAqUNH6n5RA6Ccm+FiIqIi4WheIsFUSgUuPLiDTF1LCBZArdFkrdXLxe+JhGEyJRLo6tWrCAwMxKLtm6GwKt7hmJaejikrliIpKcnA0RFRYTGZEgmybt06NG7cGMHBwVi8+hcoq1UClEU8JJVKKKtXxr3nyfDx8cHRo0eNEywR5Ys1UyITe/LkCcaMGYPIyEjs3bsXDRo0yHpB+/SX/J4ak5NSCVStADvPsli6dCl27NiBnj17YtSoUfjqq69gbc3Dm8hUeGVKZEKHDx+Gr68vSpYsiTNnzrxKpFqeZQHfmoB7yawRvkrF668rFVl/714ya7scj1/r3r07IiMjceLECbRs2RKXL182QYuICOCVKZFJZGRkYNq0aVixYgWWLVuGLl266N64hBNQp1rWWrv3HmatbKTKzJpH6uyYNWpXx2AjT09P7NmzB4sWLULTpk0xb948DBo0CAqFIs/ticgwmEyJjCw+Ph4hISFwc3NDVFQUPDw8CvdGWxugYiG3zUGpVOLjjz9GmzZtMGDAAISHh2Pp0qUoVSqP+alEZBC8zUtkJBqNBitWrECzZs0waNAghIeHFz6RGkD9+vVx+vRpeHh4wMfHBwcPHjTZZxNZGl6ZEhnBw4cPMXLkSMTHx+PgwYOoW7eukDgcHBywcOFCdOzYEQMGDMCgQYPwzTffwNbWVkg8RHLFK1MiA9u/fz98fX1RuXJlnDp1SlgizalTp06Ijo5GXFwcmjVrhosXL4oOiUhWmEyJDCQtLQ2fffYZBg0ahBUrVmD+/Pmwz7G2rmhly5bFzp07MXz4cAQEBODnn3+GJo9HvxFR0TGZEhnA33//jaZNmyI+Ph4xMTFo3759wW8SQKFQ4IMPPsDhw4exZMkSBAcHIzFR98PJiahwmEyJ9KDRaPDjjz+iZcuWGD16NH799Ve4u7uLDqtAtWrVwokTJ1CjRg34+Phg7969okMiMmscgERUTPfv38ewYcNw9+5dHD16FDVr1hQdUpHY2dlh7ty56NChA4YMGYJevXph1qxZkro1TWQueGVKVAx79uyBr68v6tWrh2PHjpldIs3pnXfeQXR0NG7cuIHGjRvj3LlzokMiMjtMpkRFkJqainHjxmHUqFFYv349Zs2aJYtpJm5ubti8eTM+/vhjtG7dGj/88AMHJxEVAZMpUSHFxMTA398f9+7dQ0xMDAIDA0WHZFAKhQLDhg3DsWPHsG7dOgQFBeHu3buiwyIyC0ymRAVQq9VYsGAB2rZtiwkTJmDjxo2yXpqvevXqOHLkCPz8/NCgQQPs2rVLdEhEkscBSET5uH37NoYMGYJnz57hxIkTqFq1quiQTMLGxgbTp09H+/btMXDgQISHh2PevHlwdHQUHRqRJPHKlEiH7du3o2HDhmjevDkOHz5sMYk0p5YtWyImJgZPnz5Fo0aNEBUVJTokIknilSnRG1JSUjB+/Hjs27cP27ZtQ/PmzUWHJJSrqyvCwsIQFhaG9u3bY+LEiRg/fjyUSv4WJ9Li0UCUQ0REBBo2bIgXL14gOjra4hNpTiEhITh9+jS2b9+Odu3a4datW6JDIpIMJlMiAJmZmZg9ezaCgoIwbdo0rF69Gi4uLqLDkhwvLy8cPHgQrVu3RsOGDbF161bRIRFJAm/zksW7ceMGBg4cCI1Gg4iICFSqVEl0SJJmbW2NyZMno127dggJCUF4eDgWLlwIZ2dn0aERCcMrU7JomzZtQqNGjdChQwccOHCAibQImjRpkj0gqUGDBjh16pTgiIjE4ZUpWaSkpCR8+OGHOH78OMLDw+Hn5yc6JLNUokQJrFixAlu2bEHXrl0xbtw4fP7557CyshIdGpFJ8cqULM7x48fRoEED2NnZITIykonUAHr16oUzZ85g//79CAwMxPXr10WHRGRSTKZkMVQqFaZNm4YePXpg3rx5+Pnnn1nnM6AKFSrgjz/+QLdu3eDv748NGzaIDonIZHiblyzClStXEBoaCicnJ0RFRcHT01N0SLKkVCrx2Wef4Z133sGAAQOwe/du/Oc//4Grq6vo0IiMilemJGsajQZr1qxBkyZN0Lt3b/z+++9MpCbQsGFDREZGwsXFBb6+vjhy5IjokIiMilemJFuPHz/GBx98gNjYWPzxxx/w8fERHZJFcXR0xI8//oj//e9/6N27N0aMGIGvvvoKNjY2okMjMjhemZIsHTp0CL6+vihTpgwiIiKYSAXq2rUroqKicOrUKbRs2RL//POP6JCIDI7JlGQlPT0dkyZNQr9+/bBkyRL88MMPcHBwEB2WxfPw8EB4eDgGDBiAZs2a4ZdffuHDx0lWmExJNi5duoSAgADExMQgOjoaQUFBokOiHJRKJcaNG4cDBw5gwYIF6NOnDx49eiQ6LCKDYDIls6fRaLBs2TIEBARg6NCh2LVrF8qVKyc6LNKhXr16OHXqFCpUqAAfHx/8+eefokMi0hsHIJFZS0xMxIgRI3D16lUcOnQItWvXFh0SFYK9vT0WLFiAjh07IjQ0FKGhoZg+fTpsbW1Fh0ZULLwyJbO1b98++Pr6omrVqjh58iQTqRnq0KEDoqOjceHCBTRr1gwXLlwQHRJRsTCZktlJS0vDp59+iqFDh2LVqlWYN28e7OzsRIdFxVSmTBls374dI0eORIsWLbB06VIOTiKzw2RKZiUuLg6NGzfG1atXERMTg7Zt24oOiQxAoVBg1KhROHLkCJYtW4bu3bvjwYMHosMiKjQmUzILGo0GixcvRmBgIMaNG4etW7fCzc1NdFhkYN7e3jh+/Dhq164NX19f/Pbbb6JDIioUDkAiybt37x6GDRuG+/fv4+jRo6hRo4bokMiIbG1tMXv2bHTo0AGDBw9GcHAw5syZA3t7e9GhEenEK1OStN27d8PX1xe+vr44duwYE6kFad26NWJiYnDnzh34+/sjNjZWdEhEOjGZkiSlpqZi7NixGD16NDZt2oSZM2dyTVcLVKpUKWzatAmffvop2rRpg4ULF0KtVosOiygXJlOSnOjoaDRq1AgPHz5ETEwMWrVqJTokEkihUGDIkCE4ceIENmzYgKCgINy5c0d0WESvYTIlyVCr1fjuu+/Qrl07TJo0CevXr0fJkiVFh0USUbVqVRw+fBhNmjRBgwYNsHPnTtEhEWXjACSShFu3bmHw4MFITU3FqVOnUKVKFdEhkQTZ2Nhg2rRpaN++PUJDQxEeHo7vvvsOTk5OokMjC8crUxLu119/RcOGDdGqVSscOnSIiZQKFBAQgOjoaDx//hyNGjVCZGSk6JDIwvHKlIRJTk7GJ598ggMHDmDHjh1o2rSp6JDIjLi6umLNmjXYsGEDOnbsiP/7v//D//3f/0Gp5DUCmR6/dSTE6dOn0bBhQ6hUKkRHRzORUrH1798fp0+fxq5du9C2bVvcuHFDdEhkgZhMyaQyMzMxa9YsdO7cGTNmzMAvv/yCEiVKiA6LzFzlypXx559/om3btvDz88PmzZtFh0QWhrd5yWSuX7+OQYMGQaFQ4MyZM6hYsaLokEhGrKysMGnSJLRr1w4hISEIDw/HokWL+GONTIJXpmQSGzduhL+/P4KCgrB//34mUjIaf39/REZGwtraGg0aNMCJEydEh0QWgFemZFRJSUkYO3YsTp48iT179qBRo0aiQyIL4OzsjGXLlmHbtm3o3r07xo4diy+++ALW1jzlkXHwypSM5ujRo/Dx8YGjoyMiIyOZSMnk3n33XURGRuLQoUMIDAzE1atXRYdEMsVkSganUqkwZcoU9OzZE99//z2WLl3KSfUkzFtvvYW9e/ciODgYjRs3xrp160SHRDLEex5kUJcvX0ZoaChcXFwQFRWF8uXLiw6JCEqlEp9++ineeecdDBgwAOHh4fjxxx+5XCUZDK9MySA0Gg1Wr16Npk2bom/fvtizZw8TKUmOr68vIiIiULp0afj6+uLw4cOiQyKZ4JUp6e3x48cYNWoUzp8/j/3796N+/fqiQyLSydHREYsXL0bHjh3Rp08fvPfee5gyZQof8Ud64ZUp6eXgwYPw8fFB+fLlcfr0aSZSMhtdunRBdHQ0IiMjERAQgPj4eNEhkRljMqViSU9Px+eff44BAwbgp59+wsKFC+Hg4CA6LKIiKVeuHHbv3o1BgwahefPmWLFiBTQajeiwyAwxmVKhnDx5Emq1GgBw8eJFNGvWDHFxcYiOjkanTp0ER0dUfAqFAmPHjsXBgwexaNEi9OrVCw8fPgQApKSkIDY2VnCEZA6YTKlAERERaNq0KebPn4+ff/4ZLVq0wPDhw7Fz506ULVtWdHhEBlGnTh2cOnUKXl5e8PX1xf79+zFw4EA0a9YMT548ER0eSZyiKLc0/Pz8NBEREUYMh0wiPQO4mwikpAKqTMDaCnByADzcAdvcgzCaN2+O48ePQ6lUonr16vj1119Rq1YtAYETmca+ffvQp08fJCcnw8rKCmPHjsW8efNyb1jEY4nMj0KhOKPRaPwK2o6jeS1JUgqQcAd49DTrzzl/SCkVwLXbgJsrULE84JK1yML+/fsRFRUFAFCr1Xjx4gW8vLxMHDiRaVWvXh3p6elQqVRQqVRYvHgxPv3001fTvYpxLJG88Tavpbh9H4i5CDx8knXgv3lHQv3y7xKfZG13+z4AoG/fvnjx4gWcnJzg4OCAO3fuIDIyUkADiExn9+7dSEtLg7OzM+zt7ZGWloa+fftmvVjMY4nkjVemluD2feDyTeDlACIASEtPx+jv5+CPM6fwKCkJVT3fwqyRY9CpSUDWdpdvQqMBGjZsiNatW6NRo0bw9vZGhQoVoFTyNxjJ25gxYzBy5EhcuXIFFy9exOHDh5GYmAjcvo/Fc7/Dqj3/Q+zVf9C/TXus+mJq9vv+++c+TPnlZ9x8cB8Vy5bDt8NHowfaZL3oyfEFcsZkKndJKbkSKQCoMjNRsUw5HPr+J1Qq54HwE0fRZ+okxK7cAK/ynoBaDcWVm9i79VegBG9TkeWxsbFBzZo1UbNmTXTr1i3rWIq5CE83N0weOAy/nz6B1LQX2dvfenAfoTO/xo6Z89CxcXOEnziK3lM/x7W6O1EWyDqOeCzJFi8x5C7hTq5ECgBODg6YOnQkvMp7QqlUokvzlqhS3hNnLl14tZFanfV+Iso+lt5t1QY9WgbCzcX1tZdvPriPks4l0KlJABQKBTo3awEnewdcvn2Tx5IFYDKVs/SMVwMkCnDv0UNcupGAOl5vv/7Cw6dZ+yGyZIU4lvxq1kKtyl7YefQQMjMzsf3wQdjZ2KL+29WzNuCxJGu8zStndxMLtVmGSoWQGV9hcMfO8K7s9fqLCgD3HgIVPQweHpHZKMSxZGVlhUHtO2PA9K/wIj0dtjbW2Dx1Npy0K4PxWJI1XpnKWUpq7pGGb1Cr1Rg482vY2thg8UcT8thAAyQ/N1KARGaiEMfSHxEnMeGnH3Dw+6VI/+MYDi38CcP/PQPR8RezNuCxJGtMpnKmysz3ZY1Gg/fmTse9x4+w9Zs5sLHWcaOigP0QyV4hjoHofy6hVf0G8POuDaVSCX/vOmhSqy7+OHOqSPsh88RkKmfWVvm+/MH82fj7+jX879v5cLCzL/Z+iGQvxzGgUqnwIi0NmepMZKrVeJGWBpVKBX/v2jh8Nir7SjQq/iIOx0ajftXqee6H5IU1UzlzcgAUijxvT12/ewc//W8b7Gxs4fFux+y//+nTLxDSLsfC9UoF4OxoimiJpCvHsTRj7UpMW70s+6V1+/ZgyuARmDp0JKYOGYleUz7HvcePUKZkSUwKGYL2/k2zNuSxJGtcm1fO0jOAE2cLrPXkS6EAmtbnOqNk2XgsWazCrs3L27xyZmsDlHYteLv8uLny4CfisUQFYDKVu0rlgeIu/6dUZr2fiHgsUb6YTOXOxQmoWgEapaJIb9MoFUDVClz+jEjr5bGkLtqhBI1SyWPJAjCZWgLPsth0+ijSMgpefUUD4EVGBrZEnuDC3ERvyCznhgU7tyAjs+ApLhoAqWlpOHH/Jo8lC8BkagHCw8MxceF3SK9dBXAvmTUQ4s0rVaUCUCigcC+JNG8vjJ83G/v27RMTMJFEzZs3D7vOnISyYe1CHUu3yjij2/vv4cqVK2ICJpPh1BiZe/DgAYYPH47169ejhKcH4ImskYn3HmatxqLKzJr75uwIlHMDbG3gCuCXX37BkCFDEBMTAzc3N9HNIBIuMjIS3333HSIiImBVsgRQskSBx1I1AJMmTcLAgQNx6NAhWOtaGIXMHqfGyJhGo0GPHj3g7e2NOXPmFPn948ePx/Xr17FlyxYoFEUsFBHJyPPnz9GoUSN8/fXX6N+/f5Heq1ar0b59ewQGBmLy5MlGipCMhVNjCMuXL0dCQgK++eabYr3/22+/RXx8PFavXm3gyIjMy4QJE9CwYcMiJ1IAUCqVWLVqFX744QecOnWq4DeQWeI9B5mKj4/HpEmTcOjQIdjZ2RVrH/b29ggLC0ObNm3QqlUrvP322wW/iUhmwsPDsWvXLkRHRxd7HxUqVMB//vMfhIaGIioqCk5OHNkrN7wylaGMjAyEhoZiypQpqF27tl77qlevXnbNR6VSGShCIvOgHXOwevVqlCxZUq999erVC82bN8enn35qoOhISphMZWjGjBkoXbo0xowZY5D9ffTRR3BwcMCsWbMMsj8ic6DRaDB8+HAMGjQI//rXvwyyz0WLFmHv3r3YuXOnQfZH0sHbvDJz/Phx/PTTT4iKijLYoCFtzadhw4bo0KEDGjdubJD9EkmZdszB5s2bDbZPFxcXrFmzBr1790bjxo3h4cEHhcsFr0xl5NmzZwgNDcXSpUtRvrxhly7LWfNJTk426L6JpEY75mD9+vWwtbU16L5btGiB9957D++99x6KMpuCpI3JVEY++ugjtGnTBj169DDK/nv37s2aD8medszB1KlTUatWLaN8xpQpU3D//n0sXbrUKPsn0+NtXpnYunUrDh8+jKioKKN+zqJFi+Dr64udO3eiW7duRv0sIhG0Yw5Gjx5ttM+wsbFBWFgYAgIC0Lp1a3h7exvts8g0eGUqA7dv38bo0aOxdu1aODs7G/WztDWfkSNH4u7du0b9LCJTO3bsGH766Sf88ssvRl+opEaNGpgxYwZCQkKQnp5u1M8i42MyNXNqtRpDhgzB6NGj0bRpU5N8ZosWLTB8+HAMGzaMNR+SjWfPnmHgwIFYunSpyQYGjRw5Ep6enpg6dapJPo+Mh8nUzC1evBjPnj3Dl19+adLPnTJlCh48eIAlS5aY9HOJjMXYYw7yolAosGLFCqxatQqHDx822eeS4bFmasbOnTuH6dOn48SJEyZfQPvNmo+xBmoQmYKpxhzkpWzZsli2bBkGDhyImJgYuLq6mjwG0h+vTM1UWloaQkJCMGfOHFStWlVIDNqaT2hoKGs+ZLa0Yw7WrVtn9DEHunTu3BlBQUH48MMPhXw+6Y/J1ExNnjwZVatWxdChQ4XGoa35TJkyRWgcRMWhHXMwZswYNGnSRGgs8+bNw6lTp7Bp0yahcVDx8DavGTpw4ADWr1+PmJgY4Y9G09Z8fHx80KlTJ7Rq1UpoPERF8cMPP+DZs2eYNGmS6FDg6OiIdevWISgoCM2bN0fFihVFh0RFwCtTM/P48WMMGTIEK1euhLu7u+hwALyq+QwaNAhPnz4VHQ5RoZw7dw4zZszAunXrJPPQbj8/P3z88ccYPHgw1Gq16HCoCJhMzYhGo8EHH3yA4OBgdOjQQXQ4r+nSpQuCgoIwduxY0aEQFUg75mDu3LnCxhzoMnHiRGRkZGDBggWiQ6EiYDI1I2FhYYiNjcXs2bNFh5KnefPm4fTp09i4caPoUIjyNXnyZFSrVg1DhgwRHUouVlZWWLt2LebMmYOYmBjR4VAhSePeBhXo2rVr+OSTT7Bv3z44ODiIDidPOWs+AQEBrPmQJB04cAAbNmxAdHS08DEHunh5eeG7775DSEgITp8+Ldljnl7hlakZyMzMxKBBgzBhwgT4+vqKDidf2prPoEGDWPMhydGOOVixYoVkxhzoEhoaijp16uCLL74QHQoVApOpGfj3v/8NKysrjB8/XnQohTJx4kSoVCrMnz9fdChE2TQaDd5//31JjjnIi0KhwJIlS7Bt2zbs3btXdDhUAN7mlbjIyEjMnz8fZ86cgZWVlehwCkVb8/H390e7du3g4+MjOiQihIWFIS4uDqtWrRIdSqGVLl0aq1atwqBBgxATEwM3NzfRIZEOvDKVsOfPnyMkJAQLFy40u/qjl5cX5s+fjwEDBiA1NVV0OGThrl27hvHjx2PdunVmV39s06YN+vXrh5EjR/LBEhLGZCphn332GRo1aoT+/fuLDqVYQkNDUbduXXz++eeiQyELZk5jDnSZOXMm4uPjzeqq2tLwNq9EhYeHY/fu3YiOjhYdSrFpaz4+Pj4ICgoyizoVyc/cuXNhbW1tNmMO8mJnZ4ewsDC0adMGrVq1ktzcWOKVqSTdv38fw4cPx+rVq1GyZEnR4ehFW/MZNmwYEhMTRYdDFubMmTNYsGABVq9eDaXSvE939erVw5dffomBAwdCpVKJDofeYN7fLhnSaDQYMWIEBg8ejH/961+iwzGId955B/3798eoUaNY8yGT0Y45WLRokdmNOdBl3LhxcHJywqxZs0SHQm9gMpWYZcuW4caNG5g2bZroUAyKNR8ytc8++wz+/v7o16+f6FAMRqlUYvXq1Vi8eDFOnjwpOhzKgTVTCbl06RK+/PJL/PXXX7C1tRUdjkGx5kOmtHv3buzevVuWy/F5enriP//5D0JDQxEVFSXsGaz0Ol6ZSkRGRgZCQ0MxdepU1KpVS3Q4RqGt+YSGhrLmQ0Zz//59jBgxAmvWrIGrq6vocIyiV69eaNGihVkPqpIbJlOJmD59Otzd3TF69GjRoRjVuHHj4OzsjG+//VZ0KCRDGo0Gw4cPx+DBg2X/bN2FCxfijz/+wI4dO0SHQuBtXkk4duwYli1bhqioKMkuvG0o2ppPgwYN0KFDBzRp0kR0SCQjy5Ytw82bN7FlyxbRoRidi4sL1q5di549e6JJkybw8PAQHZJF45WpYElJSQgNDcXSpUst5mDIWfNJTk4WHQ7JhHbMQVhYmOzGHOgSEBCAESNGYOjQoRwpLxiTqWAfffQR2rZti+7du4sOxaRY8yFD0o45mDZtmmzHHOjy9ddf4+HDh/jxxx9Fh2LReJtXoC1btuDIkSOIiooSHYoQCxcuhK+vL7Zv344ePXqIDofM2DfffAN3d3d88MEHokMxORsbG6xbtw4BAQFo06aNxf2YkApemQpy69YtjBkzBuvWrbPYoe3ams/777+PO3fuiA6HzNTRo0exfPlyrFy5UvZjDnSpUaMGZs6ciZCQEKSnp4sOxyIxmQqgVqsxdOhQjBkzxuIH4GhrPsOGDWPNh4osKSkJAwcOtKgxB7qMGDECFSpUwJQpU0SHYpGYTAVYtGgRkpOTMWnSJNGhSAJrPlRcljrmIC8KhQLLly/H6tWrcejQIdHhWBzWTE0sNjYWM2fOxIkTJ2BtzX9+gDUfKp4tW7bg6NGjiIyMFB2KZJQtWxbLly/Pfpi4uT8ow5zwytSEXrx4gZCQEMydO5fL6b2BNR8qCo450C0oKAhdunTB2LFjRYdiUZhMTWjy5MmoXr06hgwZIjoUSdLWfL7++mvRoZCEqdVqDBkyBGPHjkXjxo1FhyNJ//73vxEREYENGzaIDsVi8D6jiezfvx8bN25ETEyMxY44LIi25uNsfRYWAAAgAElEQVTr64tOnTrJ5hF0ZFiLFi1CSkoKvvjiC9GhSJajoyPCwsLQqVMnBAQEoFKlSqJDkj1emZrAo0ePMGTIEKxcuRJubm6iw5G0nDWfJ0+eiA6HJEY75mDt2rUcc1CARo0a4ZNPPsGgQYOQmZkpOhzZYzI1Mo1Gg/fffx89e/ZE+/btRYdjFljzobxwzEHRTZgwAZmZmZg/f77oUGSPydTI1q1bh/Pnz2PWrFmiQzErrPnQmzjmoOisrKywdu1azJ07F9HR0aLDkTXeJzGia9euYfz48fjjjz/g4OAgOhyzwpoP5cQxB8Xn5eWFBQsWICQkBBERETwXGQmvTI0kMzMTAwcOxMSJE+Hj4yM6HLPEmg8BHHNgCCEhIahXrx4mTpwoOhTZYjI1kjlz5sDGxoZPRdHThAkToFarWfOxUBxzYBgKhQJLlizB9u3b8dtvv4kOR5Z4m9cIIiIi8P333+PMmTNQKvl7RR9WVlZYs2YN/P390a5dO/j6+ooOiUxIO+Zg9erVokMxe6VKlcKqVaswcOBAxMTEwN3dXXRIssIzvYGlpKQgJCQEP/zwAypWrCg6HFnIWfNJTU0VHQ6ZiHbMQVhYGOt8BtKmTRv0798fI0aM4IMlDIzJ1ACSkpJw48YNAMBnn32Gxo0bo2/fvoKjkpc3az4JCQl49uyZ4KjI0O7cuYNHjx5xzIERzZw5E5cvX8Yvv/wCAPj777+hVqsFR2X+mEwN4Mcff0TVqlXxwQcfYPfu3Vi8eLHokGRHW/P59ddf8f7776Nq1ar4+eefRYdFBjZq1Ci8/fbbGDZsGMccGImdnR3Wr1+PCRMmIDQ0FLVr18aff/4pOiyzx2RqAJGRkcjIyMBPP/2E0qVL48WLF6JDkqW0tDSUKlUKP//8M1QqFaKiokSHRAYWFxeHp0+fYs2aNShXrhzS0tJEhyRL2lu869evh52dHS5cuCA4IvPHZGoAcXFxALK+oLGxsQgJCREckTz169cP58+fzz4RnDt3TnBEZEgajQY3b97M/vOmTZv4oGsjUKvVaN26NR4/fgyNRoO0tDTExsaKDsvsMZkawD///AMAcHBwwIcffojNmzcLjkietm3bhtGjR8Pe3h4AcOnSJcERkSHdvn0bGRkZUCqVKFGiBObNm4fp06eLDkt2lEolTp06hW7dumUfS0eOHBEclflTFGVEl5+fnyYiIsKI4UhUegZwNxFISQVUmYC1FeDkAHi447kqA05OTujcuTOWLl2KChUqiI5W9hISEjBq1Cj89ttvSEtLg62tbb59BFsb0SGTVj79tD18N4KDg/HRRx9h2rRpcHV1FR2t7EVFRaF///5ISEjA8+fPs/6Sx9JrFArFGY1G41fgdkym+UhKARLuAI+eZv0557+VUgFoALi5IqmkE1zeKi8kREv2+PFjlLKyLVQfoWJ5wMVJSJyEQh1LmtKuSC7tjBKeHmJitGA8lnQrbDLlog263L4PXL4J6Boyrn75RUt8ApdHSYDCCvAsa7r4CKVSM4DLVwvVR3iUBFStwD4SoZDHkuLhE5R4nARAyX4yMR5L+mPNNC95HPyhM75C+Xc7wiUoEDVCe2L5ru2vtlers7a/fV9AsBYqjz66duc2giZ+hFJd2sAjuAPGfj8XKpUq60X2kRCLZ86CX5tA2L3TFENmTX3ttecvXmD0gtlw79YWrp0D0WrcSPaTCLfvY/Hc7+A3PBR27Zrn6qf9Z07Be2AvOHZogdYfv4/rt2+xj/LAZPqmpJQ8f0V/ETIE1zbuRFL4Qeyc+R0mr1iCMxf/frWB9iTwLMXEAVsgHX00+vs5KFuyFO5s3YPo5WE4FBOJH3dsebUB+8i0klLgqbHB5NBhGNapW66XR86biUdJSfh7zWY82rkfC8Z8kvUC+8l0Xh5Lnm5umDwwdz8lPnmCd7+egOnvvY9HO/fDr2Yt9J02iX2UBybTNyXcyfNWR50qVWFnawsAUCiyFhG4fPvm6xup1VnvJ+PS0UdX79xGn9btYG9nBw83d3Rs3Axx1668vhH7yHQS7uDdloHo0TIQbi6vDya6cP0adh47jJ//bxLKlCwFKysrNKpZ69UG7CfTeHksvduqTZ79tO3wAdTxehu9A9vC3s4OU4eMRMzleFy4fo199AYm05zSM14V3/MwesFsOHZoAe9BvVHezR1BTQJyb/TwadZ+yDjy6aOPe/XHxgN78fzFC9x6cB97Th5Dx8bNcm/IPjK+Ao6lUxfiULmcB6b88jPcu7VFvaH9sPXQgdc3Yj8ZVwF9BABx167Ap2qN7D87OTigqudbr36kso+yMZnmdDcx35d//ORzPAs/hMOLluHdlq2zr1RfowBw76Fx4qN8+6iVTwPEXbsCl6BAVOjdGX41a6FHi8DcG7KPjK+AY+nmg/s4d/UyXJ2ccXvrHiz+6DMMnjUVf1+/+moj9pNxFdBHAJCcmgpXp9dH7ro6O+PZ85e3d9lH2ZhMc0pJfX04eB6srKzQor4vbj64jyU563Faag2Q/NxIAZKuPlKr1eg4YRzebdkaKb/9hcQd+/A4+Rkm/vRD7n2wj4yvgGPJwc4ONtbWmDxwGGxtbPAv30Zo3aAR9p4+8Woj9pNxFeJ85+zggKTnr9dFk1JSUMLxZYJlH2VjMs1JlVmETTNz10yLsR8qIh3/to+SkpBw7y7GBveBna0t3FxLYmjHrgg/cbRI+yEDKeDft/7b1XL9nUKhKPJ+SA+F+Let4/U2Yi7HZ/85JTUVl2/fRB2vt4u0H0vAZJqTtVWef33/8SNs3L8Xyc+fIzMzE7+fOo4NB37HOw39i7QfMgAd/7buJUuiSnlPLNmxBSqVCk+ePcPq33ejftXqRdoPGcjLf1+VSoUXaWnIVGciU63Gi7Q0qFQqtPJpiEplPTBr/SqoVCocjY3Bn1Fn0MG/WZ77ISPI8W+rq5+CW7bGuauXsfXQAbxIS8M3a5aj/tvV4V3ZK8/9WDKugJRTwh3g2u1ctz4ePHmMXlMmIuafeKg1GlQu54FxPftiRJfg3PtQKgCvt4CKXMXFKHT0EQBEx1/Ex4vnI+ZyPKyUSrRp6I8fxv0fypV2e31D9pHxveynqSt/wrTVy157acrgEZg6dCTirl7G8H/PxNkr8ahcrjxmDv8AwS1bv9qQ/WRcOY6lqb/8rLOf/og4ibEL/43r9+6iSa06WPX5FHiV98zayAL6iMsJFkd6BnDibIF1hHwpFEDT+ha5hqVJsI/MA/tJ+thHhVLYZMrbvDnZ2gCl9Vxc281V1l8s4dhH5oH9JH3sI4NiMn1TpfKAspj/LEpl1vvJuNhH5oH9JH3sI4NhMn2Ti1PWIs5F/YIplVnvK2E5T1MQhn1kHthP0sc+Mhgm07x4ls3+gql1PUUhJ+0Xi09RMJ0cfVSoig/7SIwc/VQo7CfTy3m+K0z9lH2UJyZTXTzLQuNTA3sjT0ENZI1ayyFNlQGVWg24lwR8a/KLJYJnWcC3Ji49uo/0TFWuPsqEBi/S06FxYx8J9bKf4F4ya8DKG/2Ump6OTI2Gx5JIL/so4to/Wee1N/pIpVYjXaViH+WDyTQfJ8+fw8fLFkPRtH7W8O+ypbMK9mVL4zoy0GnaRKBONd7qEKmEE/pOm4TTyhe5+khZpQJafTYGkWlP2UeilXDKOlbyOJZO3k3Ap5tX81gSLEUJtP/4AzyuWTFXH6WVd4P3kD5IqliWfaQDHw6ej/Xr1yMkJAQKO9tc86iq1qiMc6EXcOnSJdSoUUPHHsjY4uLikJiYiKYtWwJWr08eVwDo2K0r1q9fj0aNGokJkF5na5PrWKpWwhZrPhqNOfO/g52dnaDAaOfOnWjevDnKeOYeVOQEoG4DX2zfvh2DBg0yfXBmgFemOqhUKmzatAn9+/fP83UrKyv07dsXGzZsMHFklNOGDRvQr18/WFnlvQpL//79sXHjRmRmcskzqapQoQLq16+PPXv2iA7Foq1fvx4DBgzQ+fqAAQOwfv16E0ZkXphMdThw4AC8vLxQrVruNUS1tF+uoix8QYaj0WgKPAHUqlUL5cqVw19//WXCyKioeKIW6+HDhzh8+DC6d++uc5uuXbvixIkTuHfvngkjMx9MpjoUdJIGAH9/f2RmZiIyMtJEUVFOJ0+ehJ2dHRo0aJDvdiEhITxRS1yvXr3w+++/IykpSXQoFmnLli3o2LEjSpQooXMbJycndO3aFZs3bzZhZOaDyTQPqamp2LFjB/r06ZPvdgqFAgMGDEBYWJiJIqOctD948nzaSA59+/bFtm3bkJaWZqLIqKhKly6NwMBAbN++XXQoFiksLKzAiwcAPN/lg8k0D7t27YKfnx/Kly94dQ/W5MQoqKadE2ty5oG3esVISEhAXFwcOnbsWOC2bdu2xeXLl3HlyhUTRGZemEzzUJhbvFq1atWCh4cHDh06ZOSoKKfC1LRz4ola+liTE2Pjxo3o2bMnbG1tC9zWxsYGvXv35sDLPDCZvuHx48c4cOAA3n333UK/hydq0yvKDx4A6NmzJ2tyEufo6MianABFPZa0t3o58PJ1TKZv2LZtG9q2bQtX18I/TaFfv36syZlQYWvaObEmZx74w9S0tPO0W7VqVej3NGvWDM+fP8fZs2eNGJn5YTJ9g3ahhqKoUKECfHx8WJMzkaLUtHPiiVr62rZti3/++Yc1ORPZsGED+vfvD2URFrpXKpXo378/j6U3MJnmcPv2bURFRSEoKKjI7+WJ2nSKeltKizU56WNNznQKM09blwEDBmDDhg2FexCIhWAyzWHTpk3o0aMH7O3ti/xe1uRMozg1bS3W5MwDa3KmoZ2n7evrW+T31qtXD66urjh69KgRIjNPTKY5FPdXGsCanKkUp6adE+8gSB9rcqZR2HnauvBYeh2T6UuXLl3CzZs30bp162Lvg18u49PnBw/Ampw5YE3O+IoyT1uXfv36YcuWLUhPTzdgZOaLyfSlDRs2oG/fvjoXTC8M1uSM6/bt24iMjCxWTVtLW5PbuHGjASMjQ2NNzriKOk87L1WqVEGNGjWwb98+A0ZmvphMoV8hPifW5IxLW9N2cHDQaz+syUkfa3LGZYjzHcC7cTkxmQKIjIxEZmYm/P399d4Xv1zGU5xpS3lp3rw5nj9/jtjYWANERcbCBxQYR3HmaevSp08f7N69GykpKQaIzLwxmeLVIs/FLcTnxJqccRiipq2lUCjQv39/LtgtcazJGUdx52nnpUyZMmjevDl27NhhgMjMm8Un08zMTGzcuNEgtzyArJpcnz59OE/OwNavX693TTsn1uSkz8vLCzVr1sTevXtFhyIrhrrDo8W7cVksPpkeOnQI5cuXh7e3t8H2yZqcYRmqpp1T3bp1UbJkSdbkJI4nasPSztMODg422D67d++Ow4cPIzEx0WD7NEcWn0wNfZIGsubJpaamcp6cgZw5cwZqtdogNe2ceKKWvt69e2P37t1ITk4WHYosbNu2De3atSv2PO28lChRAp06dcKWLVsMtk9zZNHJNC0tDdu2bUPfvn0Nul9tTY4nasPQd3K5LqzJSV+ZMmUQEBCAnTt3ig5FFoxx8QDwhylg4cl0z549qF+/PipUqGDwfbMmZxjamrY+k8t1YU3OPGjLJqQffdYeL0jHjh0RFxeHhIQEg+/bXFh0MjV0IT4n1uQM49ChQ/Dw8ECtWrWMsn/tjx6Sru7du+PIkSMWX5PTlz5rjxfE1tYWPXv2tOjFUCw2mSYlJeH3339Hz549jfYZvPWhP2PdltLS1uQ4T066WJMzDGMfS5Z+vrPYZLp9+3YEBgaidOnSRvsM1uT0o61p9+vXz2ifoZ0nx5qctFn6iVpfhpynrUvLli2RmJiIuLg4o32GlFlsMjX2rzTgVU2Oa1cWjzFr2jnxRC19rMnpxxBrjxfEysoK/fr1s9iyiUUm03v37uHkyZPo2rWr0T+LJ+riM8UPHuDVPLmHDx8a/bOoeFiTKz5jzNPWRXu+s8Q59haZTP/73/+ia9eucHR0NPpnadeu5Dy5otHWtHv16mX0z9LW5PiAAmkLCQnhqN5iMNY87bw0aNAAdnZ2OHHihNE/S2osMpma6lcaALi7u3OeXDH8+uuvRq9p58Q7CNLXsmVLPHz4EOfOnRMdilkx1jztvCgUCos9liwumV65cgWXL1/GO++8Y7LPtNQvlz5M+YMHADp06IDz58+zJidh2oeGW2pNrjiMOU9bl/79++O///0vVCqVyT5TCiwumW7YsAF9+vSBjY2NyT6T8+SKxpQ1bS3W5MyDJdfkisMYa48XpFq1avDy8sL+/ftN9plSYFHJVKPRZD9uzZScnZ05T64ITFnTzol3EKTP19cX9vb2FlmTKw5T3+HRssRjyaKS6dmzZ5GamopmzZqZ/LMt8ctVXKJOAJY+T84cWHJNrqiMtfZ4YfTp0wc7d+5EamqqyT9bFItKpuvXr0f//v1NUoh/E2tyhaOtabdt29bkn82anHmw1JpcUe3Zswc+Pj5Gn6edl/Lly8PPzw+7du0y+WeLYjHJVK1WY8OGDUKueADW5Aprw4YN6N27t0lr2jmxJid9llqTKypRd3i0LO0OgsUk06NHj6JkyZKoW7eusBgs7ctVVKJq2jn5+vrCzs4OJ0+eFBYDFYzHUv6SkpKwd+9eo649XpB3330XBw4cwOPHj4XFYEoWk0zDwsKM9oSYwtLOk2NNLm8xMTFITU1F8+bNhcWgUCi4OIAZ6Nu3L3bu3Innz5+LDkWSTD1POy+urq5o164dtm7dKiwGU7KIZJqeno4tW7YYdcH0wtDW5PiLOm8ia9o5sSYnfR4eHvD397eomlxRiL7Fq2VJdxAsIpnu3bsXtWrVQuXKlUWHwpqcDqJr2jlVrVoVVapUYU1O4izpRF0U9+7dw6lTp9ClSxfRoSAoKAjR0dG4deuW6FCMziKSqVR+pQGAj48PHBwcOE/uDUeOHEGpUqWE1rRz4ola+oKDg/Hnn39aTE2usETN086Lvb09evTogU2bNokOxehkn0yTk5MRHh6O3r17iw4FAOfJ6SKlHzyAZc6TMzeWVpMrLKkdS5ZyvpN9Mt25cycCAgLg7u4uOpRsrMm9Tio17ZxYkzMPlnKiLiwRa48XpHXr1rh16xYuXrwoOhSjkn0yldqvNIA1uTft3bsX3t7e8PLyEh3Ka3iilj5LqskVhoi1xwtiZWWFvn37yn4xFFkn08TERBw5cgTdu3cXHUouPFG/IsUfPEBWTc6S5smZI0uqyRVECvO0dbGEgZeyTqZbtmxBp06d4OzsLDqUXFiTy5KcnIzdu3dLpqadk7Ymt23bNtGhUD74wzSLyLXHC+Lv7w+1Wo0zZ86IDsVoZJ1MpXrFA7Amp6WtaZcpU0Z0KHniiVr6LKUmVxCpzNPOiyUMvJRtMr1+/TrOnz+PDh06iA5FJ660I42VqfITFBSEqKgo1uQkzMrKCv369ZP1ibog2nnaUj6WBgwYgI0bNyIzM1N0KEYh22S6ceNG9OrVC7a2tqJD0cnS58k9ePBAsjVtLXt7ewQHB7MmJ3GWUJPLj3aedp06dUSHopO3tzfKly+PgwcPig7FKGSbTKV8i1fLxcUF7du3t9h5clu2bEFQUJAka9o5yf32lBz4+fkBACIiIgRHIoY5nO8AeR9L1qIDMKS4uDisXLkSjRs3xsOHD9GiRQvRIRVowIABWLBgARwcHHDu3DnMmjVLdEhGN3HiRPj6+mLt2rX44osvRIdToMDAQNy6dQubN2/G8ePHMWLECNSqVUt0WJSDtia3fPlynDx5EhqNBh9++KHosIwqJSUFEyZMQMeOHbF582ZERkaKDqlAffv2Rb169RAcHIzffvsN3377LVxcXESHZRgajabQ/zVq1EgjZf/73/80NjY2GhsbG42Tk5Pmyy+/1Dx+/Fh0WDodOXJE07lzZw0Ajb29vcbd3V10SCZRqlQpjb29vQaApmvXrppjx46JDkmnR48eaT7//HONo6OjxtbWVmNjY6PZs2eP6LDoDZs3b9Y0aNBAA0BjY2OjCQwMFB2S0SUmJmoUCoXGwcFBo1QqNe+9954mPj5edFg6Xb58WTNixAiNlZVVdsx37twRHVaBAERoCpEfZXWb18vLC/b29sjIyEBKSgpmz56Ny5cviw5Lp+XLl+O3334DALx48QIVKlQQHJFpeHp64sWLFwCA8PBwrFy5UnBEusXHx2Pu3Ll4/vw50tPTYW9vL7nFJQiYMWMGYmJiAAAZGRnw9vYWHJHxlS5dGra2tkhNTYVarcbKlStx4MAB0WHpdOjQISxfvhyZmZlITU2FUqlEuXLlRIdlMLJKppUrV85+vqGDgwN27dqFRo0aCY5Kt2XLlqFLly6ws7MDAFSvXl1wRKZRtWpVAICdnR2Cg4OxZMkSwRHp1rhxY+zcuTN70fCUlBRJPH2IXvfnn3+iVq1asLKyglKpRM2aNUWHZHQKhSJ7SpmDgwOmT5+OkSNHCo5Kt6FDh2LWrFlwcHAAALi7u0tyGk9xySqZlihRAgqFAtbW1ti9ezc6duwoOqR8WVtbY+vWrdmjWcuWLSs4ItPQngB69eqFTZs2wdpa2qX7zp07Y/v27bC2toa1tXX2yYCko1SpUjh27Bi8vb2hVqvh6ekpOiSTcHJyApB1Zf7ll18KjqZgEydOxOzZswG8il0upH0Wy096BnA3EUhJBVSZgLUV4OSAtv8KxIjRH6B169aiIywUKysrbNiwAY8ePULjBg2BhDu52gQPd8BWOmttFkke/TSsXRCePXyENWvWQKk0j99z7dq1Q1hYGBYuXKjzu2fW/SQDLi4uOHnyJJo0aYLa1apbxLH0zcgxiL1/G+PHjxcdXaGNGzcOt2/fxrNHj2XVRwpNEeZl+fn5aYQPPU9KyeqAR0+z/pwzfqUC0ABwcwUqlgdczOSXD9skJMQik2Ob5EaOfSS3NplZexQKxRmNRuNX4HZmlUxv3wcu3wTU6oK3VSqBqhUAT4nfOmWb2CYyDDn2kdzaZIbtKWwyNY97bEDROgHI2u7yzaz3SRXbxDaRYcixj+TWJrm15w3mkUyTUoDLN7F4y0b4jRwEu3bNMWTW1OyX0zMy0OvrifDq2w2KQH8cjHr5ZAJtZzxLERN3fl62KecXy7ljq9f+s2rTBB8u/Pfr7zODNunqpxNxsWj36RiU7voOynRvh95TPsedh4mSb9Piud/Bb3horvbk9M3qZVAE+uOPiJNZfyHlNslNHscSADxKeorgyZ/BqWNLVO7bFev/+O3190m5j3S0KfCjUbBvF5B9jqg5sOfr75Nqm3S0Z/G2/+Z5rsgm1fbkwTySacIdQK2Gp7s7Jg8chmGduuXapEU9H6z78ht4lHZ7/QW1Ouv9UvOyTTkl//ZX9n93t/0GB1s79A58J/d7Jd4mXf30ODkJI7sG49rGHbi+6X8o4eiIobOnZb0o4TZ5urnp/N4BwOVbN7H54H6Ud3N//QWptklu8jiWAGDM93Nha2ONe9t+R9iX0/HBgtmIu/rGvHOp9pGONgHA4o8+yz5PXFybx1KkUmyTjvbkd07PJsX25EH6yTQ9I7tQ/W6rNujRMhBuLq6vbWJrY4OPew9Ai/q+sFJa5d7Hw6dZ+5GKHG3SZetfB1C2VCm0rN8g7w0k3CZd/dSpSQB6B7aFi5MzHO3tMTa4D46eO/tqA4m2SVd7tMZ8PwdzRn0IW+s8RiBKrU1yo+NYSklNxda/DmD6sPfh7OiIFvV90a15K6zdG557H1Lro0KcHwokpTbl056Cjq1sUmqPDtJPpncT9d+HAsC9h/rvx1AK0abVv+/GoPaddU9qNsM2vemvmEjU8Xr71V+YYZs2H/wDdra2CGoakPcGUmuT3Ojoo0s3E2BtZYUaFV8tsOFTtTrirl3JvbHU+qiA790Xy/4D925tETD2vVclrTdJqU1yPIfnQfrzTFNSXx86XRxqDZD83DDxGEIBbbp+9w4OxURixYTJuvdhZm1609nL8fhmzQrsmDnv1V+aWZuePU/BpGU/Yt+8xbr3IbU2yY2OPkpOfQ4Xx9enVbg6O+PZ8zz6Qmp9lM/3bs6oD1HbqwpsrW2w8cBedJ00HtHLw1D1rTeWIpVSm+R4Ds+D9K9MVQZ6kKyh9mMIBcSydm84WtTzQZXyb+m1H5MqQiz/3LyBThM/wsIPP819G9uM2jR11c8Y2L4TvMoXsNqOlNokNzr+bZ0dHJH0/PVBK0kpKSjxclnIwu5HiHxiaVK7Lko4OsHO1haDO3ZBQN36CD95tMj7MSk5nsPzIP1kap1HDVTkfgyhgFjW7A3H4A5d9N6PSRUylut376Dtp2Pw1cD3MLB9ULH3YxIFxLL/zGks2roJHsEd4BHcATce3EOfaZMwZ/3qIu2H9KDj37ZGhUpQZWYi/mZC9t/FXI5/vaxQiP0IUYRYFAqF7geiS6VNcjyH50H6t3mdHACFAtBooFKpoMrMRKY6E5lqNV6kpcHaygrW1tZIS0/P/lKlqzLwIi0Ndra2WTVHpQJw1vGLVIQcbXrTsXMxuJV4P+9RvDlJuE26+une40doM/4DjA3ujfe798y9D4m2SZWRkWd79s//ERkqVfbm/u8Pxvwxn6BT4+av9iG1NsmNjmPJycEB77Zsja9X/oTln01G9D+XsOPoIRxbvCL3PqTWRzra9OTZM5z8+xz+5dMQ1lZW2PTnPvx1NgoLP/w09z6k1KZ8znf5ndNfI6X26CD9ZOrhDly7DQCYsXYlpq1elv3Sun17MGXwCEwdOhI1B/bC9XtZw6c7fJb1UOCrG3Zk3YLTACjnlmvXwuRo05tW/74b77ZsjRKOBSyjJeE26eonhUKBK7dvYeqqZZi66tXryb/9lfU/Em1Tft+7nKyUVijlXALOOW8lSq1NcpPPsfTjJxMxbM50lA1uDzcXVyz55HPUqVI194ZS6yMdbdRysuUAABskSURBVMrIVGHyiiW4kHAdVkolvCt5YfuMea8NssompTbl00eFPbYk1R4dzGM5wXP/AA+fFP/97iWBOtUMF48hsE25sU1UHHLsI7m1yYzbI6/lBCuVz1qnsTiUyqz3Sw3b9Dq2iYpLjn0ktzbJrT15MI9k6uKUteBxUTtDu1ByCfFPHsiFbXqFbSJ9yLGP5NYmubUnD+aRTIGsJwcUpTMk8sSBfLFNbBMZhhz7SG5tklt73iD9AUg5eZbN+oWScCdreSkFsibzauV8Fl6l8mbxa0bubdI8fIrUF6lwtLN/9bqZt0l1/xEy1Zmwy7l8oDm2SW5k/r2TxflBbu3JwTwGIOUlPSNreank56+e0u7smDXiywyf0g5Alm06evAgon/bjzGDh8qmTVMmfYl/1ayDNo2byqZNcnP1UjzWz1+ELz/6BOoMFTZu2Yx3B4bAvvJb5ttHcjs/mEl7CjsAybyuTHOytQEqeoiOwrBk2KbI2Ficf5oI1NIxWd4MnTgTgcYBzWXVJrmJOR+H4zevArXehhLA/GG/okqnNmhW3Ut0aMUnt/ODzNpjPjVTMkuxsbGoV6+e6DAMSo5tkps3+6hevXqIjY0VGBHJHZMpGZXcEk9iYiKeP3+OihUrig6F8sFkSqbGZEpGo1arce7cOdStW1d0KAYTGxuLunXr6n40HknC2bNncyXTs2fP5vMOIv0wmZLRXLt2DSVLlkSpUqVEh2IwcrvSlqPU1FRcv34dNWvWzP477ZVpUQZcEhUFkykZjRwTjxzbJDd///03qlWrBltb2+y/K1euHKysrHD7dt5rxBLpi8mUjEaOiUeObZKbvPpIoVCwbkpGxWRKRiO3xKNWqxEXFyerGrAc6freMZmSMTGZktHILZnKsQYsR0ymJAKTKRlFWloarl69Cm9vb9GhGIzcfhzIFZMpicBkSkbx999/4+2334adnZ3oUAyGyVT6Hj58iJSUFFSqVCnXa3Xq1MGFCxegUqkEREZyx2RKRiHHxCPHNslNfvOAnZ2d8dZbbyE+Pl5AZCR3TKZkFHJMPHJsk9wU1Ee81UvGwmRKRiG3xCPHGrAcMZmSKEymZBRyS6ZyrAHLEZMpicJkSgb3+PFjJCUloXLlyqJDMRi5/TiQI+08YCZTEoHJlAwuNjYWderUgVIpn68Xk6n0Xb9+HS4uLvnOA65WrRru3LmD5ORkE0ZGlkA+ZzuSDDkmHjm2SW4K00fW1tbw9vZGXFyciaIiS8FkSgYnx8QjxzbJTWH7iLd6yRiYTMngYmNjUb9+fdFhGIwca8ByVNjvHZMpGQOTKRmURqPBuXPnZHUVp10IQE41YDnilSmJxLMDGVRCQgKcnZ1RunRp0aEYDG/xSl9aWhquXLlSqHnA9erVw9mzZ/mgcDIoJlMyqLNnz8ou8cixTXJTlHnA5cuXh0ajwd27d00QGVkKJlMyKDlexcmxTXJTlD7ig8LJGJhMyaDklnjkWAOWo6J+75hMydCYTMmg5JZMr1+/jhIlSsiqBixHTKYkGpMpGUx6ejouX76MWrVqiQ7FYOT240CumExJNCZTMpgLFy7Ay8sL9vb2okMxGCZT6SvOPOC6devi77//RmZmphEjI0vCZEoGI8fEI8c2yU1x1oIuUaIEypUrh3/++ceIkZElYTIlg5Fj4pFjm+SmuH3EW71kSEymZDBySzxyrAHLEZMpSQGTKRmM3JKpHGvAcsRkSlLAZEoG8eTJEzx69AhVqlQRHYrByO3HgRzpMw+YyZQMicmUDOLcuXN8IDiZXEJCApycnODm5lbk99aoUQM3b95ESkqKESIjSyOfMx8JJcfEI8c2yY0+fWRjY4OaNWvi/PnzBo6KLBGTKRmEHBOPHNskN/r2EW/1kqEwmZJByC3xyLEGLEf6PtGHyZQMhcmU9KbRaGSXTOVYA5YjXpmSVPBMQXq7efMm7O3tUaZMGdGhGIzcfhzIUXp6Ov755x+95gEzmZKhMJmS3uSYeOTYJrnRzgN2cHAo9j7eeustpKen4/79+waMjCwRkynpLTY2FvXr1xcdhkHJsU1yY4g+4oPCyVCYTElvcruKk2MNWI4M1UdMpmQITKakN7klnps3b8LBwQHu7u6iQ6F8MJmSlDCZkl4yMjIQHx+P2rVriw7FYOT240CumExJSphMSS+XLl1CxYoV9RoEIjVMptJnyHnAdevWxfnz5/mgcNILkynpRd9J81IkxzbJjSHnAbu6usLNzQ1XrlwxQGRkqZhMSS9yvIqTY5vkxtB9VL9+fd7qJb0wmZJe5JZ45FgDliNDf+9YNyV9MZmSXuSWTC9evIhKlSrJqgYsR0ymJDVMplRsSUlJePDgAd5++23RoRiM3H4cyJEx5gEzmZK+mEypWNRqNc6dO4fatWvDyspKdDh6U6vVXKzBDKjVaty4ccPga0HXrFkTCQkJSE1NhVqtNth+yXIwmVKR7dixA3Z2dujevTsePHiAuXPn4saNG6LD0suQIUPg7OyMxYsX4/Dhw1i+fDnS09NFh0U5REREwM7ODn5+fsjMzMTMmTNx4cIFvfcbFRWFmTNnwtraGpUrV4adnR2uX79ugIjJkjCZUpHVr18fSqUSiYmJuH79Oj7//HMcP35cdFh68ff3R2ZmJp49e4b9+/dj7NixePLkieiwKAdvb28oFAo8ePAAiYmJ+Prrr7Fr1y6997tu3TrMmDEDycnJePDgARwcHFChQgUDREyWhMmUiqxKlSrw8PAAANjY2KBbt27o3bu34Kj007VrVygUCgCAo6Mjli9fjrJlywqOinJydnaGn58fAECpVKJRo0b45JNP9N7vjBkzULly5ew/d+zYURalCzItJlMqlp49ewIASpcujTVr1mQnInPl5eUFV1dXKBQK9OjRA6GhoaJDojwMGDAAAODg4IDt27cbJOk5ODhg9+7dsLOzg1KpRN++ffXeJ1keJlMqlnbt2gEAwsPD4eLiIjgaw2jYsCGcnJywbNky0aGQDp07dwaQdWvW09PTYPv19vbGt99+C7Vanf3dJioKhUajKfTGfn5+moiICCOGQ5KWngHcTQRSUqFRZeLR06dwq/QW4OEO2NqIjq7ocrQHqky8yFQhBWq41a5hnu2Rqzf66aGxvnfpGbh5JgYVSpYGVJmAtRXg5GC+328yCIVCcUaj0fgVuB2TKRUoKQVIuAM8epr155zfGaUC0ABwcwUqlgdcnISEWCRya49cmaqf+H2gfBQ2mVqbIhgyY7fvA5dvArrm3qlfnngSnwCPkoCqFQBPCQ/ckVt75MpU/cTvAxkIa6akW0Enmjep1Vnb375v3LiKS27tkStT9RO/D2RATKaUt6QULJ77HfyGh8KuXXMMmTU1+6Xz167Ab+QglOrSBqW6tEHb8aNx/trLx1dpTzjPUsTErUtSCnD5JhZv2Qi/kYNytenandtQBPrDuWOr7P+mr1ku3fbIVT7fu7B9e17rH8cOLaAI9MeZi38XvZ9efh/eTKR/X7+KNp98ANfOgag2IBi/Hv7z9ffx+0A68DYv5S3hDjzd3DB54DD8fvoEUtNeZL/k6VYGW6bNRmWP8lCr1fjP9s3o982XOLtyQ9YGanVWDer/27v74Djq+47jnz2dHk9PjqTTA5aBmBioQyCpgCYthJA4tYcHG8xTgJpACWUmdWk9eJjB5dkhAzjTBDNMix1SY5gQStOkwRBsEiBupjAIXKj7QLETo8GSH3TCsvV00t1u/1jLp0d0t7+9O/n2/frL0u6tvj/vWh//9vfb3y48JU/FT6GjS7JttdTXT9mmUYde+LXC4Qn/LGZjewrVJ1x31y1aousWLTn29T++9As9sPmH+sKC09xvZHKejl4PYyUSCS1dc7tuvfRybVv3mF5/9x1dcucq7djwtBa0pp5D5XrAVOiZYrLhEamnV5eff6GWnXeB6qprxm2urarSSc0tsixLjuOoKBTSrr0TlhOM9brHmQ2OtkfStG2a0WxqT6Ga4bqbaNPLW7Ti6xeNf8Y5nfM05noY63879qiz+6D+5sprVVRUpAu/cLb++LNnavPWFycfg+sBE9AzxWT7utParfair6hvcFC2Y+v+G/9i/EZL0v6Y1Nrkf32ZSrM9knTiNZfKkqVFbefokVtvU31trbthNrWnUGVwnj7c16XfvLdDT95x1/gN6ZynDH6O4zja+fvfTd7A9YAJ6Jlisv7B8Y8HTOPQllfVu+VVPXbban3+M6eO32g7Ut9AlgrMUBrtqa+p1Vt/v0kfPvuvevuJp3RkYEDXfWfML+rZ1J5CleZ1J0lPbd2i8844Syc3nzB+QzrnaZqfc+q8kxSdM0ePPLtZI4mEtr71hl5/9x0NTDEcwPWAiQhTTJZIpr1rpLxct166XCu+e68OfNzj+ThZlUYdlRUVajvtDxQOh9X4qTo9dttqbX3rDR0ZGDPRZLa0p1Bl8Pf71Msv6obFF3k7zjTbi8Nh/WztOm1549/UdPlife+5Z3TVBV/T3IZpHoXhesAY3ObFZOHM1ju1bVsDQ0Pa231Q0Tmf8nycrPFQx+g4nG2P6cHMlvYUqjT/fn/7n++qM3ZQV3z5q96O8wnbPzf/M3r9B08c+/pL375JN/zpxd5+DgKFnikmi5RLlqVEIqGheFxJO6mkbWsoHlcikdC29je144P3lUwmdbi/T6se/77mVFXp9HknpY4RsqTKirw1YZyj7ZE0bZve/O+der9jj2zbVqz3kP5q/TpdcNYfqqay0j3GbGpPoZrhuhu16eUXtPz8C1VVMcVqROmcpzHXw0Tv7f5AQ/G4BoaGtO7ZzeqKxfTNxVOEKdcDJqBnisma6qU9nVq7+Undtym16PvT217SPTd8SwtP/rRW/uARfXTwgMpLS3XO6Qv1y4cfVVlpaeoYjqTGutzXPpWj7ZE0bZtOnXei7tzwuA4c6lF1RUSL2s7Vj+9amzrGbGpPoZrhurv3xls0FI/ruVdf0T/f/9DUx0jnPI25HibavPVFbdzyc40kEjrvc2dp27rHVFpS4u3nIFBYmxdT27lLihm8HLu+dnY9h1do7SlUuTpPXA9IU7pr83KbF1Ob1yyFPF4eoZD7+dmk0NpTqHJ1nrge4DPCFFOrjriLemf6CycUcj9XNcverlFo7SlUuTpPXA/wGWGK6bVEM/uFM/qLZra+VaPQ2lOocnWeuB7gIyYg4ZO1RN3/hXd0uUuoWUq9lkoa/77Hec2z/3/shdaeQpWr88T1AJ8QpphZVcSdbDE8Iu2PKdF7RL98YYsuWnqprMoKd1ZjSXG+q0zfhPaob8B9AD9c5D7ucLy1p1Dl6jxxPcAHzOaFJ9XV1ero6FDt6Nq1AFCAmM2LrGpsbNSBA7wkGQAkwhQeRaNR7d+/P99lAMCsQJjCE3qmAJBCmMITeqYAkEKYwhN6pgCQQpjCE3qmAJBCmMKTxsZGwhQAjiJM4Qm3eQEghTCFJ9zmBYAUwhSe0DMFgBTCFJ7U1NRoaGhIQ0ND+S4FAPKOMIUnlmUpGo3SOwUAEaYwwLgpALgIU3jGuCkAuAhTeEbPFABchCk8o2cKAC7CFJ7RMwUAF2EKz+iZAoCLMIVn9EwBwEWYwjN6pgDgIkzhGT1TAHARpvCsoaFBPT09SiaT+S4FAPKKMIVn4XBYNTU1isVi+S4FAPKKMIURxk0BgDCFIcZNAYAwhaHGxkbCFEDgEaYwwmvYAIAwhSF6pgBAmMIQE5AAgDCFISYgAQBhCkP0TAGAMIUheqYAQJjC0OhsXsdx8l0KAOQNYQojkUhERUVFOnLkSL5LAYC8IUxhjHFTAEFHmMIY46YAgo4whTF6pgCCjjCFMXqmAIKOMIUxeqYAgo4whTF6pgCCjjCFMXqmAIKOMIUxeqYAgo4whTF6pgCCjjCFMXqmAIKOMIWxOXPmqK+vT8PDw/kuBQDygjCFsVAopIaGBm71AggswhS+YNwUQJARpvAF46YAgowwhS/omQIIMsIUvohGo+rs7NTevXuZiAQgcAhTGHnttdfU2tqqRx99VGvWrFFra6vWr1+f77IAIKcIUxhZsGCBuru7NTIyIsdxVFpaqmXLluW7LADIKcIURlpaWvTggw+qrKxMknTmmWdq/vz5ea4KAHKLMIWxlStXKhqNSpJWrVqV52oAIPcIUxgLh8PasGGDysrKtHTp0nyXAwA5F853ASgAwyP6+mlnaOCd/5L1fx1SuEiKlEtN9VJJcb6rA4CsI0zh3eF+qaNL6umVJFmOk9oWsqQ9nVJdjdTaLFVH8lQkAGQfYQpvOg9Iuz+SbHvq7fbRYO0+JPUclubPlVqiuasPAHKIMVNkbqYgnci23f07WSEJQGEiTJGZw/3TBumzv9qq01dcqcji8zT/2mXa/t6O1MbRQD3Sn8NiASA3uM2LzHR0TRmk29rf1B1PrNdP7n5Q55y+UF2x7smftW338wtPyUGhAJA7hCnSNzxybLLRRPf86B9094qb9UcLz5AkndAwzfhorNc9DrN8ARQQbvMiffum6G1KSiaTan//f3Tw0Mc65drLNPeKi/SX339Yg/GhyTtbkvbHslsnAOQYYYr09Q9KYx9/OWr/xz0aSST0/Ou/1vb1G/QfG5/Rjl3va+3mJycfw3akvoEcFAsAuUOYIn2J5JTfLi8tlSStvPwqNdfVq762VquuvE4vvvHbjI4DAMcrwhTpCxdN+e05VdWa2xCVZVnHvjfmj2kfBwCOV4Qp0hcpnzYlb1xyidb/9Cc68HGPPj5yWH/3Tz/WxV/8k8k7hiypsiLLhQJAbjGbF+lrqneXCJzCXStuVnfvIS24frnKSkp01VcWac31N03e0ZHUWJfdOgEgxyxnigkl02lra3Pa29uzWA5mvZ27pNgh75+vr+U5UwDHDcuy3nYcp22m/bjNi8zMa5ZCHi+bUMj9PAAUGMIUmamOuIvWZxqooZD7uSreHgOg8BCmyFxLNLNAHQ1S3hoDoEAxAQnetETdXmZHl7tEoKXUa9ckd9auI/d9pvOa6ZECKGiEKbyririTiYZH3CUC+wb06iuv6PNnn63aE5rdWbuswQsgALjNC3MlxVJrk3T6p7V60xP6oCjhfk2QAggIwhS+qqysVF9fX77LAICcIkzhq0gkov5+XgAOIFgIU/iKMAUQRIQpfEWYAggiwhS+qqysJEwBBA5hCl9FIhEmIAEIHMIUvuI2L4AgIkzhK27zAggiwhS+omcKIIgIU/iKMVMAQUSYwlf0TAEEEWEKXzFmCiCICFP4ip4pgCAiTOErxkwBBBFhCl/RMwUQRIQpfMWYKYAgIkzhK3qmAIKIMIWvKioqNDAwINu2810KAOQMYQpfhUIhlZeXa3BwMN+lAEDOEKbwHbd6AQQNYQrfEaYAgoYwhe941hRA0BCm8B2PxwAIGsIUvuM2L4CgIUzhO8IUQNAQpvAdY6YAgoYwhe8YMwUQNIQpfMdtXgBBQ5jCd4QpgKAhTOE7xkwBBA1hCt8xZgogaAhT+I7bvACChjCF77jNCyBoCFP4jp4pgKAhTOE7xkwBBA1hCt/RMwUQNIQpfMeYKYCgIUzhO3qmAIKGMIXvGDMFEDSEKXzHbV4AQUOYwndlZWUaGRlRMpnMdykAkBOEKXxnWZYqKiq41QsgMAhTZAWTkAAECWGKrKisrGTcFEBgEKbICnqmAIKEMEVWEKYAgoQwRVYQpgCChDBFVjBmCiBICFNkBT1TAEFCmMJXtm0rFovJtm3t2rVL7e3tGhwczHdZAJBVhCl8tX79ejU0NOj555/XQw89pHPPPVdbtmzJd1kAkFWEKXx19dVXH1tOMB6Pq7KyUhdffHG+ywKArCJM4aumpibdfvvtKi4uVlFRkVauXKmysrJ8lwUAWWU5jpP2zm1tbU57e3sWy0EhGBgYUENDg+LxuDo7OxWNRvNdEgB4YlnW247jtM20XzgXxSBYKioqtHr1am3fvp0gBRAI9Ezhv+ERaV+31D8oJZJSuEiKlEtN9VJJcb6rA4C00TNF7h3ulzq6pJ5e9+ux/1ELWdKeTqmuRmptlqoj+akRALKAMIU/Og9Iuz+SbHvq7fbRYO0+JPUclubPlVq4BQygMDCbF+ZmCtKJbNvdv/NAdusCgBwhTGHmcL8ee/h7arv5epUu+pK++d17x23e+MLPdMq1l6ly8flavHqlOrsPuhtGA/UISw4COP4RpjDT0aWWujr97Z/dpJuWXDpu02s73tadGx/Xz7+zTj2/+JVObj5B33hgTWoH23bHWAHgOEeYwrvhEamnV5eff6GWnXeB6qprxm1+4d+368oLvqqFJ89XSXGx7lrx5/rNuzu0e+9HqZ1ive5xAOA4RpjCu33dM+4y9tGr0T/v/P3u1A6WpP0xvysDgJwiTOFd/+D4x18mWHzOF/Xcq6/ovd0faDA+pPuf2ijLsjQQH0rtZDtS30AOigWA7CFM4V0i+Ymbv9Z2ru678RYtv/sOnXTNUp3U1KyqigrNbZjwSMwMxwGA2Y4whXfhohl3+fZlV+mDZ36q/f/yspaff6ESyaQ+e/L8jI8DALMZYQrvIuWSZSmRSGgoHlfSTipp2xqKx499b+fvdslxHHXs36db1j2o25ZfozlV1aljhCypsiJ/bQAAH7ACErxrqpf2dGrt5id136YNx7799LaXdM8N39JfX/ENXbv2Lu3u/EhV5RW6cckleuCmW8cfw5HUWJfbugHAZyx0DzM7d0mxQ94/X18rLTzFv3oAwEfpLnTPbV6YmdcshTxeRqGQ+3kAOM4RpjBTHXEXrc80UEMh93NVvD0GwPGPMIW5lmhmgToapLw1BkCBYAIS/NESdXuZHV3uEoGWUq9dk9xZu47c95nOa6ZHCqCgEKbwT1XEnUw0POIuEdg34C7IEC5yH39prJNKivNdJQD4jjCF/0qKpdamfFcBADnDmCkAAIYIUwAADBGmAAAYIkwBADBEmAIAYIgwBQDAEGEKAIAhwhQAAEOEKQAAhghTAAAMEaYAABgiTAEAMESYAgBgiDAFAMAQYQoAgCHCFAAAQ4QpAACGCFMAAAwRpgAAGCJMAQAwRJgCAGCIMAUAwBBhCgCAIcIUAABDhCkAAIYIUwAADBGmAAAYIkwBADBEmAIAYIgwBQDAEGEKAIAhwhQAAEOEKQAAhghTAAAMEaYAABgiTAEAMGQ5jpP+zpZ1UNKH2SsHAIBZ5UTHcRpm2imjMAUAAJNxmxcAAEOEKQAAhghTAAAMEaYAABgiTAEAMESYAgBgiDAFAMAQYQoAgCHCFAAAQ/8P2YsnRMpZwlgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 576x720 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import random\n",
    "random.seed(1)\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def create_graph(G, node, pos={}, x=0, y=0, layer=1):\n",
    "    pos[node.value] = (x, y)\n",
    "    if node.left:\n",
    "        G.add_edge(node.value, node.left.value)\n",
    "        l_x, l_y = x - 1 / 2 ** layer, y - 1\n",
    "        l_layer = layer + 1\n",
    "        create_graph(G, node.left, x=l_x, y=l_y, pos=pos, layer=l_layer)\n",
    "    if node.right:\n",
    "        G.add_edge(node.value, node.right.value)\n",
    "        r_x, r_y = x + 1 / 2 ** layer, y - 1\n",
    "        r_layer = layer + 1\n",
    "        create_graph(G, node.right, x=r_x, y=r_y, pos=pos, layer=r_layer)\n",
    "    return (G, pos)\n",
    "\n",
    "def draw(node):   # 以某个节点为根画图\n",
    "    graph = nx.DiGraph()\n",
    "    graph, pos = create_graph(graph, node)\n",
    "    fig, ax = plt.subplots(figsize=(8, 10))  # 比例可以根据树的深度适当调节\n",
    "    nx.draw_networkx(graph, pos, ax=ax, node_size=300, node_color = 'pink')\n",
    "    plt.show()\n",
    "\n",
    "class node:\n",
    "    def __init__(self,x):\n",
    "        self.value = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "\n",
    "def randomTree(nums):\n",
    "    def addLeaf(root,t):\n",
    "        if random.randint(0,1) == 0:\n",
    "            if not root.left:\n",
    "                root.left = node(t)\n",
    "            else:\n",
    "                addLeaf(root.left,t)\n",
    "        else:\n",
    "            if not root.right:\n",
    "                root.right = node(t)\n",
    "            else:\n",
    "                addLeaf(root.right,t)\n",
    "    if len(nums) == 0:\n",
    "        return None\n",
    "    root = node(nums[0])\n",
    "    \n",
    "    print(nums)\n",
    "    for t in nums[1:]:\n",
    "        addLeaf(root,t)\n",
    "    return root\n",
    "N = 20\n",
    "root = randomTree(random.sample(range(N),k = N))\n",
    "draw(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 2, 18, 3, 8, 16, 10, 11, 7, 12, 14, 0, 5, 1, 13, 15, 17, 9, 6, 19]"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## Non-recursive BFS with queue\n",
    "from queue import Queue\n",
    "def bfs(root):\n",
    "    his = []\n",
    "    if not root:\n",
    "        return None\n",
    "    q = Queue()\n",
    "    q.put(root)\n",
    "    while not q.empty():\n",
    "        l = q.qsize()\n",
    "        for _ in range(l):\n",
    "            n = q.get()\n",
    "            if n.left:\n",
    "                q.put(n.left)\n",
    "            if n.right:\n",
    "                q.put(n.right)\n",
    "            his.append(n.value)\n",
    "    return his\n",
    "\n",
    "bfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {0: [4],\n",
       "             1: [2, 18],\n",
       "             2: [3, 8, 16, 10],\n",
       "             3: [11, 7, 12, 14, 0, 5, 1],\n",
       "             4: [13, 15, 17, 9],\n",
       "             5: [6],\n",
       "             6: [19]})"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## recursive BFS\n",
    "from collections import defaultdict\n",
    "def level_order_traversal(node):\n",
    "    res = defaultdict(list)\n",
    "    def search(node,level):\n",
    "        if not node:\n",
    "            return None\n",
    "        res[level].append(node.value)\n",
    "        \n",
    "        if node.left:\n",
    "            search(node.left,level + 1)\n",
    "        if node.right:\n",
    "            search(node.right,level + 1)\n",
    "    search(node, 0)\n",
    "    return res\n",
    "\n",
    "level_order_traversal(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Preorder [4, 2, 3, 11, 7, 8, 12, 13, 6, 19, 14, 15, 18, 16, 0, 17, 9, 10, 5, 1]\n",
      "Inorder [11, 3, 7, 2, 13, 6, 19, 12, 8, 15, 14, 4, 16, 17, 0, 9, 18, 5, 10, 1]\n",
      "Postorder [11, 7, 3, 19, 6, 13, 12, 15, 14, 8, 2, 17, 9, 0, 16, 5, 1, 10, 18, 4]\n"
     ]
    }
   ],
   "source": [
    "## recursive DFS\n",
    "def recursive_DFS(root, method):\n",
    "    res = []\n",
    "    def visit(root):\n",
    "        if not root:\n",
    "            return\n",
    "        if method == 'pre': res.append(root.value)\n",
    "        if root.left: visit(root.left)\n",
    "        if method == 'in': res.append(root.value)\n",
    "        if root.right: visit(root.right)\n",
    "        if method == 'post': res.append(root.value)\n",
    "    visit(root)\n",
    "    return res\n",
    "\n",
    "print('Preorder',recursive_DFS(root,'pre'))\n",
    "print('Inorder',recursive_DFS(root,'in'))\n",
    "print('Postorder',recursive_DFS(root,'post'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Preorder [4, 2, 3, 11, 7, 8, 12, 13, 6, 19, 14, 15, 18, 16, 0, 17, 9, 10, 5, 1]\n",
      "Ineorder [11, 3, 7, 2, 13, 6, 19, 12, 8, 15, 14, 4, 16, 17, 0, 9, 18, 5, 10, 1]\n",
      "Ineorder [11, 7, 3, 19, 6, 13, 12, 15, 14, 8, 2, 17, 9, 0, 16, 5, 1, 10, 18, 4]\n"
     ]
    }
   ],
   "source": [
    "## Non-recursive DFS with stack\n",
    "def Preorder_traversal(root):\n",
    "    his = []\n",
    "    if not root:\n",
    "        return None\n",
    "    stack = [root]\n",
    "    while stack:\n",
    "        n = stack.pop()\n",
    "        his.append(n.value)\n",
    "        if n.right:\n",
    "            stack.append(n.right)\n",
    "        if n.left:\n",
    "            stack.append(n.left)\n",
    "    return his\n",
    "\n",
    "def Inorder_traversal(root):\n",
    "    his = []\n",
    "    if not root:\n",
    "        return None\n",
    "    stack = []\n",
    "    n = root\n",
    "    while stack or n:\n",
    "        while n:\n",
    "            stack.append(n)\n",
    "            n = n.left\n",
    " \n",
    "        \n",
    "        n = stack.pop()\n",
    "        his.append(n.value)\n",
    "        n = n.right\n",
    "    return his\n",
    "\n",
    "def Postorder_traversal(root):\n",
    "    his = []\n",
    "    if not root:\n",
    "        return None\n",
    "    stack = []\n",
    "    current = root\n",
    "    while stack or current:\n",
    "        while current:\n",
    "            stack.append(current)\n",
    "            current = current.left\n",
    "            \n",
    "        current = stack[-1]\n",
    "        if not current.right or current.right == previous:\n",
    "            his.append(current.value)\n",
    "            previous = current\n",
    "            current = None\n",
    "            stack.pop()\n",
    "        else:\n",
    "            current = current.right\n",
    "    \n",
    "    return his\n",
    "\n",
    "print('Preorder',Preorder_traversal(root))\n",
    "print('Ineorder',Inorder_traversal(root))\n",
    "print('Ineorder',Postorder_traversal(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
